1400E - Clear the Multiset - CodeForces Solution

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
 
//#define int long long 
#define endl '\n'
#define x first
#define y second
 
using namespace std;
 
const int N = 5010, M = 15, mod = 1e9+7, INF = 0x3f3f3f3f3f3f3f3f;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<long long , long long> PLL;

typedef pair<char,int> PCI;
typedef pair<int,pair<int,int>> PIII;
typedef pair<string,int> PSI;
typedef pair<double,double> PDD;
 
int n,m;
int a[N];
int f[N][N];//表示在第i个位置使用了j次操作1的最小答案
int mn[N];

void solve()
{ 
   cin>>n;
   for (int i=1;i<=n;i++)cin>>a[i];
   memset(f,0x3f,sizeof f);
   f[0][0]=0;
   for (int i=1;i<=n;i++)
   {
       mn[n+1]=INF;
       for (int j=n;j>=0;j--)mn[j]=min(mn[j+1],f[i-1][j]);
       int x = INF;
       for (int j=0;j<=min(a[i],n);j++)
       {
           x=min(x,f[i-1][j]-j);
           f[i][j]=min(mn[j],x+j)+(j<a[i]);
       }
   }
   int ans =  INF;
   for (int i=0;i<=min(a[i],n);i++)ans=min(ans,f[n][i]);
   cout<<ans<<endl;
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    //init(N-1);
    int T=1;
    //cin>>T;
    while (T--) solve();
    return 0; 
}